import numpy as np
import copy
import matplotlib.pyplot as plt
from Core.init_city_index_distance import *
from Core.GA import *

'''
旅行商要走一遍经过所有城市，而且最后要回到原来出发的城市。求最短路线。
其在数学中其被定义为NP 困难问题，在运筹学和理论计算机科学中非常重要。
'''


def get_last_dist(city_index, dist_mat):
    distance = 0.0
    for i in range(0, len(city_index) - 1):
        from_city = city_index[i]
        to_city = city_index[i + 1]
        # 找到矩阵中相应的距离并累加到fitness
        distance += dist_mat[from_city, to_city]
    # 由题意知最后还要回到起点
    distance += dist_mat[city_index[-1], city_index[0]]

    return distance


# 迭代轮数
my_iter = 1000
# 城市数量
city_num = 15
# 种群数量
population_num = 50
# 交叉率 [0,1] **建议设置大一些
cross_rate = 0.1
# 交叉点 [0, city_num - 1] -> 单点交叉, 两个体互换交叉点后面基因座上的基因
cross_point = 7
# 变异率 [0, 1] -> 变异提供了搜索随机性, 但不可调过大
mutation_rate = 0.05

index_dict = index_dict_init(city_num)
# 获得城市间距离矩阵
dist_mat = distance_matrix_init(index_dict, city_num)

# 实例化对象
my_ga = GA(city_num=city_num, index_dict=index_dict, dist_mat=dist_mat, population_num=population_num,
           cross_rate=cross_rate, cross_point=cross_point, mutation_rate=mutation_rate)

population_list = []
lines_list = []
dist_list = []
for _ in range(my_iter):
    p_list = my_ga.init_population(population_list)
    p_select = my_ga.select(p_list)
    p_cross = my_ga.cross(p_select)
    p_mutation = my_ga.mutation(p_cross)
    population_list = p_mutation
    # 获得某一代的最佳结果
    individual_ = my_ga.get_best_individual(population_list)
    # 获得某一代最佳的搜索路线, 因为最终路线需要回到起点, 此处不能改变源基因序列, 要用深拷贝
    res_line = copy.deepcopy(individual_.genes)
    res_line.append(res_line[0])
    # 记录迭代过程中搜索的路径
    lines_list.append(res_line)
    dist_list.append(get_last_dist(res_line, dist_mat))

# 最后迭代结果
result_line = lines_list[-1]
city_index = []
# 像index_dict查询城市对应坐标, 封装列表
for city in result_line:
    city_index.append(index_dict.get(city))

x = []
y = []
for city in city_index:
    x.append(city[0])
    y.append(city[1])

# 绘图
# 路线图
# lines_fig = plt.figure()
# plt.plot(x, y, 'r-o')
# plt.plot(x[0], y[0], 'b-o')
# plt.title('line')
# plt.legend()
# lines_fig.show()

# 算法效果（距离）
plt.figure(figsize=(8, 5))
plt.plot([i for i in range(len(dist_list))], dist_list)
plt.legend()
plt.show()
